package com.company.ljh.easy;

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 对称二叉树 {


    /**
     * 1.递归
     *  1节点1的左子树必须和节点2的右子树对称，节点1的右子树必须和节点2的左子树对称
     *  2节点左根节点和右根节点值必须相同
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null || node1.val != node2.val) {
            return false;
        }
        //节点1的左子树必须和节点2的右子树对称，节点1的右子树必须和节点2的左子树对称
        return compare(node1.left, node2.right) && compare(node1.right, node2.left);
    }
    /**
     * 2.循环
     *
     *  与递归类似，使用队列存储节点，每次取出两个节点进行对比，每次两个节点子节点交替入队
     *
     * @param
     * @return
     */

    public boolean compare2(TreeNode node) {
        LinkedList<TreeNode> queue = new LinkedList();
        queue.push(node);
        queue.push(node);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.pop();
            TreeNode node2 = queue.pop();
            if (node1 == null && node2 == null) {
                continue;
            }
            if (node1 == null || node2 == null || node1.val != node2.val) {
                return false;
            }
            queue.push(node1.left);
            queue.push(node2.right);
            queue.push(node1.right);
            queue.push(node2.left);
        }
        return true;
    }
}
